#ifndef __MULTICONJ_STOCK_H__
#define __MULTICONJ_STOCK_H__

#ifndef NULL
#define NULL 0
#endif

#include <iostream>
#include <cassert>
#include "defines.h"

using namespace std;

class multiconj_stock{
public:
	multiconj_stock(nat cant);
	//multiconj_stock(); //constructor por defecto, no deberia usarse!
	~multiconj_stock();
	bool vacio() const;
	void agregar(material m, nat c);
	void sacar(material m, nat c);
	nat cardinal(material m) const;
	material elQueMasHay() const;
	void actualizarStock(int* arr);
	nat cantMateriales() const{return tam;}
	
	//esto es solo para testing! no se deben usar..
	void mostrar(ostream&) const;
	void printList() const;
	void printHeap() const;

private:
	struct tupla{
		int cant;
		int enHeap; //indice de la posicion del elemento en el heap
	};
	nat tam;
	tupla* cantidad; //array: los indices representan el numero de material, y su contenido es la tupla con la cantidad disponible de ese material, y un "pointer" a la posicion de ese material en el heap
	int* heap; //el heap, es un array que contiene los numeros de los materiales, ordenados como un heap para sacar el maximo (ej: los hijos de la posicion p son 2*p+1 2*p+2, donde cantidad[p].cant > cantidad[hijos].cant)
	
	int subir(nat pos);
	int bajar(nat pos);
	void swap(nat m,nat n);
};

//multiconj_stock::multiconj_stock():tam(0),cantidad(NULL),heap(NULL){} //Necesario poner los arrays en null, sino se rompe todo con el delete!!

multiconj_stock::multiconj_stock(nat cant):tam(cant),cantidad(new tupla[cant]),heap(new int[cant]){
	//inicializo todos los materiales en 0; el heap queda 0,1,2,3... pero da lo mismo cualquier orden
	for(int i=0;i<tam;i++){
		cantidad[i].cant=0;
		cantidad[i].enHeap=i;
		heap[i]=i;
	}
}

multiconj_stock::~multiconj_stock(){
	delete [] cantidad;
	delete [] heap;
}

bool multiconj_stock::vacio() const{
	bool res=true;
	int i=0;
	while(i<tam && res){
		if(cantidad[i].cant>0)res=false;
		i++;
	}
	return res;
}

void multiconj_stock::agregar(material m, nat c){
	assert(m<tam);
	cantidad[m].cant+=c; //sumo la cantidad agregada
	subir(cantidad[m].enHeap); //modifico el heap porque probablemente la cantidad del elemento m sea mayor a la de su padre en el heap
}

int multiconj_stock::subir(nat pos){
	//mientras la cantidad del material sea mayor a la de su padre, los intercambio (reestablece el invariante)
	while(pos>0 && cantidad[heap[(pos-1)/2]].cant<cantidad[heap[pos]].cant){
		swap(pos,(pos-1)/2);
		pos=(pos-1)/2;
	}
	return pos;
}

void multiconj_stock::swap(nat m, nat n){
	//intercambio las posiciones en el heap
	int tmp=heap[m];
	heap[m]=heap[n];
	heap[n]=tmp;
	//importante: actualizo los pointers en al array de cantidades
	cantidad[heap[m]].enHeap=m;
	cantidad[heap[n]].enHeap=n;
}

void multiconj_stock::sacar(material m, nat c){
	assert(m<tam);
	if(cantidad[m].cant<c)cantidad[m].cant=0;
	else cantidad[m].cant-=c;
	bajar(cantidad[m].enHeap); //intenta bajar el material en el heap por si su cantidad queda menor que la de alguno de sus hijos
}

int multiconj_stock::bajar(nat pos){
	//mientras haya un hijo con cantidad mayor, lo intercambio por el hijo que tenga mas cantidad (reestablece el invariante)
	while((2*pos+1<tam && cantidad[heap[2*pos+1]].cant > cantidad[heap[pos]].cant) || (2*pos+2<tam && cantidad[heap[2*pos+2]].cant > cantidad[heap[pos]].cant)){
		if(2*pos+2<tam && cantidad[heap[2*pos+2]].cant > cantidad[heap[2*pos+1]].cant){
			swap(pos,2*pos+2);
			pos=2*pos+2;
		}else{
			swap(pos,2*pos+1);
			pos=2*pos+1;
		}
	}
	return pos;
}

nat multiconj_stock::cardinal(material m) const{
	assert(m<tam);
	return cantidad[m].cant;
}

material multiconj_stock::elQueMasHay() const{
	assert(tam>0);
	return heap[0]; //el elemento que esta bien arriba del heap es del que hay mas cantidad
}

void multiconj_stock::actualizarStock(int* arr){
	//toma un array con valores nuevos para todas las cantidades de los materiales
	
	//actualizo todas las cantidades
	for(int i=0;i<tam;i++){
		cantidad[i].cant=arr[i];
		cantidad[i].enHeap=i;
		heap[i]=i;
	}
	
	//rearmo el heap considerando que esta totalmente desarmado (algoritmo de floyd)
	int pos=(tam-1)/2;
	while(pos>=0){
		bajar(pos);
		pos--;
	}
}

void multiconj_stock::mostrar(ostream& out) const{
	out << "[";
	for(int i=0;i<tam;i++){
		out << i << "->" << cantidad[i].cant << (i<tam-1?", ":"");
	}
	out << "]";
}

void multiconj_stock::printList() const{
	for(int i=0;i<tam;i++){
		std::cout << i << ":" << cantidad[i].cant << ", ";
	}
	std::cout << std::endl;
}
void multiconj_stock::printHeap() const{
	for(int i=0;i<tam;i++){
		std::cout << heap[i] << " ";
	}
	std::cout << std::endl;
}

ostream& operator<<(ostream& out, const multiconj_stock& ms) {
	ms.mostrar(out);
	return out;
}


#endif
